//********************************************************************
//        KJH/ HS  23.01.07
// Kjedet implementasjon av en mengde. Læreboka kap. 4.4
//********************************************************************

import java.util.*;

class KjedetMengde<T> implements MengdeADT<T>
{
  private static Random rand = new Random();
  private int antall;  // antall elementer i mengden 
  private LinearNode<T> start; 

  /******************************************************************
    Oppretter en tom mengde.
  ******************************************************************/
  public KjedetMengde() 
  {
    antall   = 0;
    start    = null;
  }

  /******************************************************************
    Legger til elementet til denne mengden hvis den ikke allerede er med.
   
  ******************************************************************/
  public void leggTil (T element)
  {
    if (!(inneheld(element)))
    {
      LinearNode<T> node = new LinearNode<T> (element);
      node.settNeste(start);
      start = node;
      antall++;
    }
  }

  /******************************************************************
    Legger mengden til denne mengden.
  ******************************************************************/
  public void leggTilAlle (MengdeADT<T> m2)
  {
    Iterator<T> teller = m2.oppramsar();

    while (teller.hasNext())
         leggTil(teller.next());
  }

  /******************************************************************
    Fjerner og returnerer et tilfeldig element.
  ******************************************************************/
    
  public T fjernTilfeldig(){
    LinearNode<T> forgjenger, aktuell;
    T resultat = null;

    if (!erTom()){
        
    int valg = rand.nextInt(antall) + 1;
    if (valg == 1)
    {
      resultat = start.hentElement();
      start = start.hentNeste();
    }
    else
    {
      forgjenger = start;
      for (int nr=2; nr < valg; nr++)
          forgjenger = forgjenger.hentNeste();
      aktuell  = forgjenger.hentNeste();
      resultat = aktuell.hentElement();
      forgjenger.settNeste(aktuell.hentNeste());
    }
    
    antall--;
    
    }//if

    return resultat;
  }
	
  
  

  /******************************************************************
    Fjerner og returnerer spesifisert element fra denne mengden..
  ******************************************************************/
  public T fjern (T element)
  {
    boolean funnet = false;
    LinearNode<T> forgjenger, aktuell=null;
    T resultat = null;

    if (!erTom()){
            
       if (start.hentElement().equals(element)) {// /Sletter foran
          resultat = start.hentElement();
          start = start.hentNeste();
          antall--;
       }
       else{ // Gjennomgår den kjedete strukturen
          forgjenger = start;
          aktuell = start.hentNeste();
          for (int søk = 1; søk < antall && !funnet; søk++){
              if (aktuell.hentElement().equals(element))
                  funnet = true;
              else{
                  forgjenger = aktuell;
                  aktuell = aktuell.hentNeste();
              }
		  }
		  if(funnet){
		  	  resultat = aktuell.hentElement(); // Sletter midt inni eller bak
              forgjenger.settNeste(aktuell.hentNeste());
              antall--;
		  }
          
       }//if -else
     }//if ikke-tom 
     return resultat;
   }
  
  /******************************************************************
   Returnerer en ny mengde som er unionen av denne mengden og parameteren.
   parameter.
  ******************************************************************/
  public MengdeADT<T> union (MengdeADT<T> m2)
  {
    KjedetMengde<T> begge = new KjedetMengde<T>();
    LinearNode<T> aktuell = start;
    
    while (aktuell != null){
      begge.leggTil (aktuell.hentElement());
      aktuell = aktuell.hentNeste();
    }
    
   Iterator<T> teller = m2.oppramsar();
    while (teller.hasNext())
      begge.leggTil (teller.next());
    
    return begge;
  }
  
  /******************************************************************
    Returnerer sann hvis mengden inneholder det spesifiserte elemntet.
    element.
  ******************************************************************/
  public boolean inneheld (T element)
  {
    boolean funnet = false;
    LinearNode<T> aktuell = start;
    
    for (int søk =0; søk < antall && !funnet; søk++){
      if (aktuell.hentElement().equals(element))
        funnet = true;
      else
        aktuell = aktuell.hentNeste();
    }
    return funnet;
  }
  
 /******************************************************************
    Returnerer sann hvis de to mengdene er like.
   .
  ******************************************************************/ 
 
   public boolean erLik(MengdeADT m2){
        boolean likeMengder = true;       
        T element= null;

        if(antal()== m2.antal()){
        	
           Iterator<T> teljar = m2.oppramsar();
            
            while (teljar.hasNext() && likeMengder){
            	element = teljar.next();
            	if(!this.inneheld(element)){
            		likeMengder = false;
            	}//if
            	
            }//while
            
        }//if
        else{
        	likeMengder = false;
        }
         
       return likeMengder;   
              
    } 
    
      
  /******************************************************************
    Returnerer sann hvis mengden er tom og usann ellers.
  ******************************************************************/
  public boolean erTom()
  {
    return (antal() == 0);
  }
 
  /******************************************************************
    Returnerer antall elementer i den kjedete strukturen.
  ******************************************************************/
  public int antal(){
    return antall;
  }

  /******************************************************************
    Returnerer en iterator for elemntene i mengden..
  ******************************************************************/
  public Iterator<T> oppramsar(){
    return new KjedetIterator<T> (start, antall);
  }

  /******************************************************************
    Returnerer en streng som representerer mengden. 
  ******************************************************************/
  public String toString()
  {
    String resultat = "";

    LinearNode<T> aktuell = start;

    while (aktuell != null) {
      resultat += aktuell.hentElement().toString() + "\t";
      aktuell = aktuell.hentNeste();
    }

    return resultat;
  }
}


class Bingo{
// Lager to like mengder
    public static void main(String[] a){
        
        
        final int ANTAL_BALLAR=75, ANTAL_TREKK=5;
        
        KjedetMengde <Bingokule>miMengde1 = new 
                     KjedetMengde<Bingokule>();
                     
        KjedetMengde <Bingokule>miMengde2 = new
                      KjedetMengde<Bingokule>();
        
        Bingokule kule1  = null;
        Bingokule kule2  = null;
       
        for(int i=1; i <= ANTAL_BALLAR; i++){
        	kule1 = new Bingokule(i);
        	kule2 = new Bingokule(i);
           miMengde1.leggTil(kule1);
           miMengde2.leggTil(kule2);
        }
       
        System.out.println("\nAntal kuler totalt: " + 
                           miMengde1.antal());
        System.out.println();
        kule1 = new Bingokule(1);
        if(miMengde1.inneheld(kule1))
          System.out.println("Kule 1 som er "+ kule1+" funne i mengde 1.");
          
        if(miMengde1.erLik(miMengde2))
          System.out.println("Dei to mengdene er like.\n"); 
        else
          System.out.println("Dei to mengdene er ikkje like.\n");
          
        miMengde1.fjern(kule1);
        System.out.println("Har fjerna kule 1 i mengde 1.");
        if(miMengde1.erLik(miMengde2))
          System.out.println("Dei to mengdene er like.\n"); 
        else
          System.out.println("Dei to mengdene er ikkje like.\n");
          
        
        
        
    }
}